Error correction and detection has great practical importance in communication systems. Various noise and other impairments may occur in the transmission and reception of signals in the communication system. Error detection and correction methods can help minimize the effects of transmission errors by detecting, locating and correcting them.
A variety of error-correction schemes can be provided that are computationally intensive, or require excessive redundancies in the data coding scheme. Error correction methodologies in some applications, such as a sender-receiver system, are achieved with a detection system that works in tandem with an automatic repeat request scheme that notifies the sender that a portion of the data sent was received incorrectly and will need to be retransmitted. A variety of schemes can be employed for error-detection such as repetition, parity, and cyclic redundancy.
In an example repetition schemes, the transmission data is broken into blocks that are repeatedly sent. For example, if we want to send a data block of “1101”, we may repeat transmission of this block three times each, yielding the following non-ideal result: “1101”, “1111”, and “1101”. For this example, one of the data blocks has an error that can be corrected by detecting the anomaly in one of the three data blocks.
An example parity scheme includes one or more parity bits included in the transmitted blocks to ensure that the data is valid. The data is broken up into blocks of bits, and the total number of “1” bits is counted for the data block. A “parity bit” is added to the transmission block, where the party bit is set to a “1” or cleared to a “0” based on the number of one bits being odd or even. When consecutive transmission blocks overlap, the parity bits can be used to isolate and often correct the error.
A cyclic redundancy (CRC) check scheme can be used to provide more powerful error detection. The cyclic redundancy check scheme evaluates each block of data and identifies polynomial coefficients based on the data. The polynomial coefficients are applied to generate a polynomial, which is then by a fixed polynomial. The coefficients that result from the division are used as the redundant data bits in the CRC field of the data transmission, which includes a payload with the original data. When the transmission is received, the CRC field can be verified by comparing it to a computed CRC from the payload data bits. Alternatively, the data from the payload can be checked by multiplying the fixed polynomial with the CRC and comparing it to the received data payload.
An error-correcting code or ECC is a code in which each data signal conforms to specific rules of construction so that departures from this construction can be detected in the received signal and appropriately corrected. Examples of error-correcting codes include: Hamming codes, Reed-Solomon codes, Reed-Muller codes, Binary Golay codes, as well as others. The simplest error correcting codes can correct single-bit errors (single error correction), while other error correcting codes can correct multi-bit errors and/or multi-word errors.